package algorithm.middle;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @BelongsProject: LeetCode
 * @BelongsPackage: algorithm.middle
 * @Author: 江岸
 * @CreateTime: 2021-09-03 22:01
 * @Description: 设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。
 *
 * 示例：
 *
 * 输入： arr = [1,3,5,7,2,4,6,8], k = 4
 * 输出： [1,2,3,4]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/smallest-k-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class SmallestK {

    public static int[] smallestK(int[] arr, int k) {
        if(k==0) return new int[0];
        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.comparing(o-> -o));
        for (int i=0;i<arr.length;i++){
            if (pq.size()<k){
                pq.add(arr[i]);
            }else {
                Integer num = pq.peek();
                if (arr[i]<num){
                    pq.poll();
                    pq.add(arr[i]);
                }
            }
        }
        return  pq.stream().mapToInt(Integer::valueOf).toArray();
    }

    public static void main(String[] args) {
        smallestK(new int[]{1,2,3,4,5,6,7,8},4);
    }
}
